import java.util.*;
/**
 * 
 * 有重复项数字的全排列
 * 
 * 描述

给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。

数据范围： 
0
<
n
≤
8
0<n≤8 ，数组中的值满足 
−
1
≤
v
a
l
≤
5
−1≤val≤5
要求：空间复杂度 
O
(
n
!
)
O(n!)，时间复杂度 
O
(
n
!
)
O(n!)
 */

public class 有重复项数字的全排列 {
    
    public static void main(String[] args) {
        
        int[] nums = new int[]{1,1,2};

        permuteUnique(nums);

        //输出打印结果
        for (List<Integer> permutation : permutations) {
            for (int num : permutation) {
                System.out.print(num+"  ");
            }
            System.out.println();
        }
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
    public static ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        // write code here

        //用于标记某数字是否使用过
        Arrays.sort(num);
        boolean[] used = new boolean[num.length];
        backtrack(permutations, current, num, used);

        return permutations;
    }

    //创建一个二维列表，赋全排列的值
    static ArrayList<ArrayList<Integer>> permutations = new ArrayList<>();
    //表示当前排列
    static ArrayList<Integer> current = new ArrayList<>();

    private static void backtrack(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> tempList, int[] nums, boolean[] used) {
        if (tempList.size() == nums.length) {
            result.add(new ArrayList<>(tempList));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] &&!used[i - 1])) {
                continue;
            }
            used[i] = true;
            tempList.add(nums[i]);
            backtrack(result, tempList, nums, used);
            used[i] = false;
            tempList.remove(tempList.size() - 1);
        }
    }
}
